package com.zhupf.heap;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhupf
 * @date 2024年02月27日 16:20
 * @Description
 *
 *  347. 前 K 个高频元素
 */
public class TopKFrequent {


    public static void main(String[] args) {
        TopKFrequent topKFrequent = new TopKFrequent();
        int[] nums = {4,1,-1,2,-1,2,3};
        int[] ints = topKFrequent.topKFrequent(nums, 2);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }



    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        int[] ans = new int[k];
        int idx = 0;
        for (Integer integer : countMap.keySet()) {
            if(idx<k){
                ans[idx] = integer;
                this.addHeap(ans,idx,countMap);
            }else {
                if(countMap.get(integer) > countMap.get(ans[0])){
                    ans[0] = integer;
                    minHeapify(ans,0,k,countMap);
                }
            }
            idx++;
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = ans[i];
        }
        return ret;
    }

    private void addHeap(int[] heap,int len,Map<Integer, Integer> countMap) {
        int child = len;
        while (child > 0){
            int parent = (child-1)/2;
            if(countMap.get(heap[parent]) <= countMap.get(heap[child])){
                break;
            }
            int tmp = heap[child];
            heap[child] = heap[parent];
            heap[parent] = tmp;
            child = parent;
        }
    }

    private void minHeapify(int[] maxHeap, int parent, int len,Map<Integer, Integer> countMap) {
        while (parent * 2 + 1 < len) {
            int child = parent * 2 + 1;
            if ((child + 1) < len && countMap.get(maxHeap[child + 1]) < countMap.get(maxHeap[child])) {
                child += 1;
            }
            if (countMap.get(maxHeap[parent]) <= countMap.get(maxHeap[child])) {
                break;
            }
            int tmp = maxHeap[parent];
            maxHeap[parent] = maxHeap[child];
            maxHeap[child] = tmp;
            parent = child;
        }
    }
}
